package algorithm.leetcode.I101to200;

import algorithm.leetcode.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class Q106 {

    // 存储中序遍历节点的位置,key-节点值,value-中序遍历索引
    Map<Integer, Integer> inorderMap = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);

    }

    private TreeNode build(int[] inorder,
                           int inorderStart,
                           int inorderEnd,
                           int[] postorder,
                           int postorderStart,
                           int postorderEnd) {
        // 递归终点
        if (inorderEnd < inorderStart) return null;

        // 拿到根节点
        TreeNode root = new TreeNode(postorder[postorderEnd]);
        // 拿到根节点在中序遍历的位置
        int rootIndex = inorderMap.get(postorder[postorderEnd]);
        // 计算左右子树在数组中的长度
        int leftLen = rootIndex - inorderStart;
        int rightLen = inorderEnd - rootIndex;
        // 递归整理左子树
        root.left = build(inorder, inorderStart, rootIndex-1, postorder, postorderStart, postorderStart+leftLen-1);
        // 递归整理右子树
        root.right = build(inorder, rootIndex+1, inorderEnd, postorder, postorderStart+leftLen, postorderStart+leftLen+rightLen-1);
        return root;

    }
}
